# 作者: 家里蹲 吴越洋
# 2023年03月02日08时58分19秒
import random
class Sort():
    def __init__(self,len):
        self.arr=[]
        self.len=len
        self.arr_random()

    def arr_random(self):
        for i in range(self.len):
            self.arr.append(random.randint(0,99))

    def print_arr(self):
        for i in self.arr:
            print(i,end=' ')

    def heap_adjust(self,adjust,len):
        arr=self.arr
        dad=adjust
        son=dad*2+1 #左孩子
        while son<len:
            if son+1<len and arr[son+1]>arr[son]:
                son+=1

            if arr[son]>arr[dad]:
                arr[son],arr[dad]=arr[dad],arr[son]
                dad=son
                son=2*dad+1
            else:
                break


    def heap_sort(self):
        arr = self.arr
        # 调整堆变为一个大根堆
        for i in range(self.len // 2 - 1, -1, -1):
            self.heap_adjust(i, self.len)
        arr[0], arr[self.len - 1] = arr[self.len - 1], arr[0]
        for len in range(self.len-1,1,-1):
            self.heap_adjust(0,len)
            arr[0], arr[len - 1] = arr[len - 1], arr[0]

if __name__ == '__main__':
    sort = Sort(10)
    sort.print_arr()
    print('\n')
    sort.heap_sort()
    sort.print_arr()